In many memory devices, including random access memory (RAM) devices, data is typically accessed by supplying an address to an array of memory cells and then reading data from the memory cells that reside at the supplied address. However, in content addressable memory (CAM) devices, data within a CAM array is not accessed by initially supplying an address, but rather by initially applying data (e.g., search words) to the array and then performing a search operation to identify one or more entries within the CAM array that contain data equivalent to the applied data and thereby represent a “match” condition. In this manner, data is accessed according to its content rather than its address. Upon completion of the search operation, the identified location(s) containing the equivalent data is typically encoded to provide an address (e.g., block address+row address within a block) at which the matching entry is located. If multiple matching entries are identified in response to the search operation, then local priority encoding operations may be performed to identify a location of a best or highest priority matching entry. Such priority encoding operations frequently utilize the relative physical locations of multiple matching entries within the CAM array to identify a highest priority matching entry.
The cells within a CAM array are frequently configured as binary CAM cells that store only data bits (as “1” or “0” logic values) or as ternary (or quaternary) CAM cells that store data bits and mask bits. As will be understood by those skilled in the art, when a mask bit within a ternary CAM cell is inactive (e.g., set to a logic 1 value), the ternary CAM cell may operate as a conventional binary CAM cell storing an “unmasked” data bit. When the mask bit is active (e.g., set to a logic 0 value), the ternary CAM cell is treated as storing a “don't care” (*) value, which means that all compare operations performed on the actively masked ternary CAM cell will result in a cell match condition. Thus, if a logic 0 data bit is applied to a ternary CAM cell storing an active mask bit and a logic 1 data bit, the compare operation will indicate a cell match condition. A cell match condition will also be indicated if a logic 1 data bit is applied to a ternary CAM cell storing an active mask bit and a logic 0 data bit. Accordingly, if a data word of length N, where N is an integer, is applied to a ternary CAM array having a plurality of entries therein of logical width N, then a compare operation will yield one or more match conditions whenever all the unmasked data bits of an entry in the ternary CAM array are identical to the corresponding data bits of the applied search word. This means that if the applied search word equals {1011}, the following entries will result in a match condition in a CAM comprising ternary CAM cells: {1011}, {*011}, {1*11}, {10*1}, {101*}, {**11}, {1**1}, . . . , {1***}, {****}.
A quaternary CAM cell is different from a ternary CAM cell because it has four valid combinations of states: ((data=0, mask=active), (data=1, mask=active), (data=0, mask=inactive), (data=1, mask=inactive)). Quaternary CAM cells are frequently treated as “ternary” CAM cells because two of the four states represent equivalent active mask conditions when search operations are performed. However, ternary CAM (TCAM) cells and quaternary CAM (QCAM) cells will be treated herein as separate categories of CAM cells.
CAM cells may be configured with NOR-type or NAND-type compare logic. In the case of NOR-type compare logic, a match line associated with a row of CAM cells is typically switched high-to-low upon detection of at least one “miss” in the row during a search operation. NOR-type compare logic typically provides for faster CAM cell operation during search operations with relatively high match line power consumption. Because of the parallel configuration of NOR-type compare logic, parasitic leakage currents through the compare logic transistors may provide a significant pull-down force on a match line and lead to search failure.
In contrast, in NAND-type compare logic, a match line signal is propagated across the compare logic and lower match line power is typically consumed. For example, in the conventional ternary NAND-type CAM cell 10 of FIG. 1A, a match line signal may be propagated across at least one of two parallel paths of a four transistor (4T) compare logic circuit when a match condition is present or blocked from propagation when a miss condition is present. A first one of these two parallel paths is defined by transistor NA, which is responsive to a data signal (DX) applied during a search operation, and transistor NB, which is responsive to a signal generated at a storage node of an X memory cell (SRAM SX). A second one of these two parallel paths is defined by transistor NC, which is responsive to a data signal (DY) applied during a search operation, and transistor ND, which is responsive to a signal generated at a storage node of a Y memory cell (SRAM SY).
Unfortunately, because CAM cells having the NAND-type compare logic illustrated by FIG. 1A require serial propagation of match line signals, NAND-type CAM devices are typically slower in operation relative to NOR-type CAM devices. This serial propagation of a match line signal is demonstrated by the pair of NAND-type CAM cells 10′ of FIG. 1B. This pair of CAM cells 10′ includes a left cell containing transistors NA1, NB1, NC1 and ND1 and a right cell containing transistors NA2, NB2, NC2 and ND2. A worst case propagation of a match line signal ML from the left of the left cell to the right of the right cell requires a propagation through four serially-connected transistors NA1, NB1 (or NC1, ND1) and NA2, NB2 (or NC2, ND2).
FIG. 2A illustrates another NAND-type CAM cell 20, which is illustrated and described more fully in U.S. Pat. No. 7,110,275 to Park, the disclosure of which is hereby incorporated herein by reference. This CAM cell 20 includes four memory cells and a ladder-type compare circuit. The four memory cells are illustrated as static random access memory (SRAM) cells (SXA, SXB, SXC and SXD). The ladder-type compare circuit contains four parallel rungs for the case where four bits of data are stored within the CAM cell 20. The first rung includes two NMOS transistors connected in series (i.e., source-to-drain). These two NMOS transistors are shown as T1 and T2. This first rung becomes conductive to thereby short a left side match line segment (MLa) to a right match line segment (MLb) when an applied data signal DXA and an output (e.g., storage node output) of the memory cell SRAM SXA are both set to logic 1 values. Similarly, the second rung of the compare circuit includes transistors T3 and T4. This second rung becomes conductive when an applied data signal DXB and an output of the memory cell SRAM SXB are both set to logic 1 values. The third rung of the compare circuit includes transistors T5 and T6. This third rung becomes conductive when an applied data signal DXC and an output of the memory cell SRAM SXC are both set to logic 1 values. The fourth rung of the compare circuit includes transistors T7 and T8. This fourth rung becomes conductive when an applied data signal DXD and an output of the memory cell SRAM SXD are both set to logic 1 values.
As illustrated by FIG. 2B, NAND-type CAM cells may be provided in a CAM system 22 having a large capacity CAM array 26 therein. The CAM array 26 may be configured to support a large number of rows and columns of NAND-type CAM cells. The data and bit lines (e.g, DXA, DXB, DXC and DXD and (BXA, BXBA), (BXB, BXBB), (BXC, BXBC) and (BXD, BXBD)) that span the CAM array 26 are electrically coupled to a bit/data line encoder and driver circuit 24. The bit lines that span the CAM array 26 may also be electrically coupled to a bit/data line decoder and buffer circuit 28, which receives data from the CAM array 26 during read operations. As illustrated, the encoder/driver circuit 34 receives input data and the decoder/buffer circuit 28 generates output data.